package org.usmile.algorithms.knapsack;

public class _0_1_Knapsack4 {
    public int solve(int[] costs, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < costs.length; i++) {
            for (int c = capacity; c >= costs[i]; c--) {
                dp[c] = Math.max(dp[c], dp[c - costs[i]] + values[i]);
            }
        }

        return dp[capacity];
    }

    public static void main(String[] args) {
        _0_1_Knapsack4 k = new _0_1_Knapsack4();
        int[] w = {3, 4, 5, 2};
        int[] v = {15, 10, 12, 8};
        System.out.println(k.solve(w, v, 10));
    }
}
